home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d13 / ptv2n1.arc / L4.C < prev    next >
Text File  |  1991-03-26  |  1KB  |  35 lines
  1. /* Finds and returns the greatest common divisor of two integers.
  2.    Uses Euclid's Algorithm: divides the larger integer by the
  3.    smaller; if the remainder is 0, the smaller integer is the gcd,
  4.    otherwise the smaller integer becomes the larger integer, the
  5.    remainder becomes the smaller integer, and the process is
  6.    repeated. Avoids code recursion. */
  7.  
  8.  
  9. unsigned int gcd(unsigned int int1, unsigned int int2) {
  10.    unsigned int temp;
  11.  
  12.    /* Swap if necessary to make sure that int1 >= int2 */
  13.    if (int1 < int2) {
  14.       temp = int1;
  15.       int1 = int2;
  16.       int2 = temp;
  17.    }
  18.  
  19.    /* Now loop, dividing int1 by int2 and checking the remainder,
  20.       until the remainder is 0. At each step, if the remainder isn't
  21.       0, assign int2 to int1, and the remainder to int2, then
  22.       repeat */
  23.    for (;;) {
  24.       /* If the remainder of int1 divided by int2 is 0, then int2 is
  25.          the gcd */
  26.       if ((temp = int1 % int2) == 0) {
  27.          return(int2);
  28.       }
  29.       /* Make int2 the larger integer and the remainder the
  30.          smaller integer, and repeat the process */
  31.       int1 = int2;
  32.       int2 = temp;
  33.    }
  34. }
  35.